package org.example.myleet.p1449;

public class Solution {
    public String largestNumber(int[] cost, int target) {
        //dp[i][j]表示在选择第i个cost时，且总cost恰为j时能表示的最大数字
        String[][] dp = new String[cost.length + 1][target + 1];
        //初始化
        for (int i = 0; i <= cost.length; ++i) {
            //cost恰为0，代表全都不选，都是""
            dp[i][0] = "";
        }
        for (int j = 0; j <= target; ++j) {
            //全都不选，都是""
            dp[0][j] = "";
        }
        for (int i = 0; i < cost.length; ++i) {
            int c = cost[i];
            for (int j = 1; j <= target; ++j) {
                if (j < c) {
                    //不选cost[i]，此时最大数字从dp[i][j]继承过来
                    dp[i + 1][j] = dp[i][j];
                } else {
                    //newNum表示可能可以形成的新数字
                    String newNum = "";
                    if (dp[i + 1][j - c].length() == 0) {
                        if (j % c == 0) {
                            //j消耗恰好可以由x个cost[i]组成，在前头叠加本次数字(i + 1)
                            newNum = (i + 1) + dp[i + 1][j - c];
                        }
                        //如果dp[i + 1][j - c] = ""，而j消耗不可以由x个cost[i]组成，则不能叠加本次数字，仍然为""
                    } else {
                        //j消耗可以由之前的某些数字组成，也就是可以在前头叠加本次数字(i + 1)
                        newNum = (i + 1) + dp[i + 1][j - c];
                    }
                    //选 或 不选 本次叠加数字，取更大的数字作为dp[i + 1][j]能得到的数字
                    dp[i + 1][j] = max(dp[i][j], newNum);
                }
            }
        }
        //注意空字符串时返回0
        return dp[cost.length][target].length() == 0 ? "0" : dp[cost.length][target];
    }

    /**
     * 比较两个字符串数字哪个更大，返回更大的，相等时返回第一个，两个都是空字符串时返回空字符串
     */
    private String max(String num1, String num2) {
        if (num1.length() < num2.length()) {
            return num2;
        } else if (num1.length() > num2.length()) {
            return num1;
        }
        if (num1.length() == 0) {
            return "";
        }
        for (int i = 0; i < num1.length(); ++i) {
            if (num1.charAt(i) < num2.charAt(i)) {
                return num2;
            }
            if (num1.charAt(i) > num2.charAt(i)) {
                return num1;
            }
        }
        return num1;
    }
}
